package com.code.leetcode._202507;

import java.util.Deque;
import java.util.LinkedList;

// 42: 接雨水 困难
public class Trap {
    /**
     * 给定一个n个非负整数表示每个宽度为1的柱子的高度图，计算按此排序的柱子，下雨之后能接多少雨水
     * 示例1：输入：height=[0,1,0,2,1,0,1,3,2,1,2,1]
     * 输出：6
     * 解释：上面是有数组[0,1,0,2,1,0,1,3,2,1,2,1]表示的高度图，在这种情况下，可以接6个单位的雨水
     * 示例2：输入：height=[4,2,0,3,2,5]
     * 输出：9
     **/
    public static void main(String[] args) {
        Trap t = new Trap();
        System.out.println(t.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }

    /**
     * 动态规划
     * 对于下标i，下雨后水能到达的最大高度等于下标i两边的最大高度的最小值，下标i处能接的雨水量等于下标i处
     * 的水能到达的最大高度减去height[i]
     * 朴素的做法是对于数组height中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个
     * 下标的位置能接的雨水量，假设数组height的长度为n，该做法需要对每个下标位置使用O(n)的时间向两边扫描并
     * 得到最大高度，因此时间复杂度是O(n^2)
     * 上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置的两边的最大高度，则可以
     * 在O(n)的时间内得到能接的雨水总量。使用动态规划的方法，可以在O(n)的时间内预处理得到每个位置两边的最大高度。
     * 创建两个长度为n的数组leftMax和rightMax。对于0<=i<=n，leftMax[i]表示下标i及其左边的位置中，height的
     * 最大高度，rightMax[i]表示下标i及其右边的位置中，height的最大高度。
     * 显然，leftMax[0]=height[0]，rightMax[n-1]=height[n-1]。两个数组的其余元素的计算如下
     * 1、当1<=i<=n-1时，leftMax[i]=max(leftMax[i-1],height[i])
     * 2、当1<=i<=n-2时，rightMax[i]=max(rightMax[i+1],height[i])
     * 因此可以正向遍历数组height得到数组leftMax的每个元素值，方向遍历数组height得到数组rightMax的每个元素值。
     * 在得到数组leftMax和rightMax的每个元素值之后，对于0<=i<=n，下标i处能接的雨水量等于
     * min(leftMax[i],rightMax[i])-height[i]。遍历每个下标位置即可得到能接的雨水总量
     **/
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }

    /**
     * 单调栈
     * 除了计算并存储每个位置两边的最大高度以外，也可以用单调栈计算能接的雨水总量
     * 维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组height中的元素递减
     * 从左到右遍历数组，遍历到下标i时，如果站内至少有两个元素，记栈顶元素为top，top的下面一个元素是left，则
     * 一定有height[left]>=height[top]。如果height[i]>height[top]，则得到一个可以接雨水的区域，
     * 该区域的宽度是i-left-1，高度是min(height[left],height[i])-height[top],根据宽度和高度即可计算
     * 得到该区域能接的雨水量。
     * 为了得到left，需要将top出栈。在对top计算能接的雨水量之后，left变成新的top。重复上述操作，直到栈变为空，
     * 或者栈顶下标对应的height中的元素大于或等于height[i].
     * 在对下标i处计算能接的雨水量之后，将i入栈，继续遍历后面的下标，计算能接的雨水量，遍历结束之后即可得到能接的雨
     * 水总量。
     **/
    public int trap1(int[] height) {
        int ans = 0;
        Deque<Integer> stack = new LinkedList<>();
        int n = height.length;
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && (height[i] > height[stack.peek()])) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
        }
        return ans;
    }

    /**
     * 双指针
     * 动态规划的做法中，需要维护连个数组leftMax和rightMax，因此空间复杂度是O(n)。是否可以将空间复杂度降到O(1)
     * 注意到下标i处能接的雨水量由leftMax[i]和rightMax[i]中的最小值决定。由于数组leftMax是从左到右计算，数组rightMax
     * 是从右往左计算，因此可以使用双指针和两个变量代替两个数组。
     * 维护两个指针left和right，以及两个变量leftMax和rightMax，初始时left=0，right=n-1，leftMax=0，rightMax=0.
     * 指针left只会向右移动，指针right只会向左移动，在移动指针的过程中维护两个变量leftMax和rightMax的值。
     * 当两个指针没有相遇时，进行如下操作：
     * 1、使用height[left]和height[right]的值更新leftMax和rightMax的值
     * 2、如果height[left]<height[right],则必有leftMax<rightMax,下标left处能接的雨水量等于leftMax-height[left],
     * 将下标left处能接的雨水量加到能接的雨水总量，然后left加1（即向后移动一位）
     * 3、如果height[left]>=height[right],则必有leftMax>=rightMax,下标right处能接的雨水量等于rightMax-height[right]，
     * 将下标right处能接的雨水量加到能接的雨水总量，然后将right减1（即向左移动一位）
     * 当两个指针相遇时，即可得到能接的雨水总量
     **/
    public int trap2(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax,height[left]);
            rightMax = Math.max(rightMax,height[right]);
            if (height[left] < height[right]){
                ans += leftMax - height[left];
                ++left;
            }else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
}
